import treeUnit from '../unit/TreeUnit.js'
var arr = [8, 3, 5, 7, 2, 4, 6, 1]
/**
 * 插入法建堆
 */
function heapInsert(arr) {
    let result = []
    for (let i in arr) {
        result.push(arr[i])
        let child = result.length
        let parent = Math.floor(child / 2)
        while (result[child - 1] > result[parent - 1]) {
            let temp = result[child - 1]
            result[child - 1] = result[parent - 1]
            result[parent - 1] = temp
            child = Math.floor(child / 2)
            parent = Math.floor(child / 2)
        }
    }
    return result
}

/**
 * 堆化(调整法建堆)
 */
function heapify(len) {
    for (let i = Math.floor(len / 2); i >= 1; i--) {
        let parent = i
        let lagerChild = 2 * parent
        while (lagerChild <= len) {
            if (lagerChild < len && arr[lagerChild - 1] < arr[lagerChild]) {
                lagerChild++
            }
            if (arr[lagerChild - 1] > arr[parent - 1]) {
                swap(lagerChild - 1, parent - 1)
                parent = lagerChild
                lagerChild = 2 * parent
            } else {
                break
            }
        }
    }
}
/**
 * 交换节点值
 */
function swap(i1, i2) {
    let temp = arr[i1]
    arr[i1] = arr[i2]
    arr[i2] = temp
}

console.log('---原数组---')
treeUnit.printTree(arr)
console.log('---插入法建堆---')
treeUnit.printTree(heapInsert([8, 3, 5, 7, 2, 4, 6, 1]))
console.log('---调整法建堆---')
heapify(arr.length)
treeUnit.printTree(arr)